package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 插入排序</p>
 *
 * @author tanzc
 * @date 2021/12/27
 **/
public class InsertionSort {
    public static void main(String[] args) {
        InsertionSort insertionSort = new InsertionSort();
        int num = 1000000, max = num * 5;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
//        ArrayUtils.printArray(arr1);

        System.out.print("插入排序-----time: ");
        Date start = new Date();
        insertionSort.insertion(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        ArrayUtils.printArray(arr1);
    }

    /**
     * 插入排序，跟选择排序相似之处在于，都可以把序列看成有序与无序两部分
     * 然后不断把无序序列元素并入有序序列
     *
     * 每轮排序，取无序序列第一个元素，记为tmp
     * 从有序序列尾部向前比较，比tmp大的依次后移，直到找到tmp的位置
     * @param arr
     */
    public void insertion(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
//            while (j >= 0) {
//                if (arr[j] > tmp) {
//                    arr[j + 1] = arr[j];
//                    j--;
//                } else {
//                    break;
//                }
//            }
            while (j >= 0 && arr[j] > tmp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}
